//
//  SearchPro_OC.m
//  AlgorithmPro
//
//  Created by kingcode on 26/10/2017.
//  Copyright © 2017 kingcode. All rights reserved.
//


#import "SearchPro_OC.h"

/*
 你真的会写二分检索吗？   http://blog.chinaunix.net/uid-1844931-id-3337784.html
 */
// 最简单的二分查找
int binarySearch(int a[], int key, int length) {
    int left = 0;
    int right = length - 1;
    
    while (left <= right) {
        int mid = (right + left) >> 1;// 另一种方式 left + ((right - left) >> 1); 化简就成了
        if (key < a[mid]) {
            right = mid - 1;
        } else if (key > a[mid]) {
            left = mid + 1;
        } else {
            return mid;
        }
    }
    
    return -1;
}

/**
 搜索第一个或者最后一个的，关键是看把如果等于了也不终止循环的条件加载左边，还是右边。
 如果加在左边，也就是会不断地往右边缩小范围，这个是找到最后一个相等的
 如果加在右边，也就是不断地往左边缩小范围，这个是找到第一个相等的
 */
int binarySearhFirst(int *a, int key, int length) {
    int left = 0;
    int right = length - 1;
    while (left <= right) {
        int mid = (left + right) >> 1;
        if (a[mid] < key) {
            left = mid + 1;
        } else if(a[mid] >= key) {
            //找到第一个，也就是不断的往左边变小。也就是把right变小，
            right = mid -1;
        }
    }
    
    if (left < length - 1 && a[left] == key) {
        return left;
    }
    return -1;
}

int binarySearhLast(int *a, int key, int length) {
    int left = 0;
    int right = length - 1;
    while (left <= right) {
        int mid = (left + right) >> 1;
        if (a[mid] <= key) {
            //找到最后，也就是不断的往右边找。也就是把left变大，
            left = mid + 1;
        } else if(a[mid] > key) {
            right = mid -1;
        }
    }
    
    if (right < length - 1 && a[right] == key) {
        return right;
    }
    return -1;
}

// 非常不程序员
double f(int n, double a[], double x) {
    int i = 0;
    double p = a[0];
    for (i = 1; i <= n; i++) {
        p += a[i] * pow(x, i);
    }
    return p;
}

//从里往外计算
double f1(int n, double a[], double x) {
    int i = 0;
    double p = a[n];
    // 非常巧妙，类似递归
    for (i = n; i > 0; i--) {
        p = a[i - 1] + x * p;
    }
    return p;
}

// 类似于文章扩展
void MyPrint(int n) {
    if (n <= 0) {
        return;
    }
    printf("%d \n", n);
    MyPrint(n - 1);
    printf("%d \n", n);
    
}

int sumD(int n) {
    if (n == 1) {
        return 1;
    }
    return n + sumD(n - 1);
}

static double sum = 0;
int fd(int n, int a[], int x) {
    if (n <= 0) {
        return a[0];
    }
    return a[n - 1] + x * fd(n - 1, a, x);
    
}

//
double Polynomail(int a[], int i, double x, int n)
{//本算法计算多项式的值, a[]代表多项式的每一项的系数
    //i代表多项式的阶次, x代表每一项的幂, n代表多项式的项数  项数和阶次一样
    if (i > 0)
    {
        // 每次变化的地方是阶次
        return a[n - i] + Polynomail(a, i - 1, x, n) * x;//拆分原理
    }
    else
    {
        return a[n];
    }
}

//冒泡排序
void pubble_sort(int a[], int lenght) {
    for (int i = 0; i < lenght - 1; i++) {
        for (int j = 0; j < lenght - 1 - i; j++) {
            //交换
        }
    }
}

//插入
void insert_Sort(int a[], int length) {
    for (int i = 1; i < length; i++) {
        int temp = a[i];//抽牌
        int j;
        for (j = i - 1; temp < a[j]; j--) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = temp;
        
    }
}
@implementation SearchPro_OC

- (void)testFunc {
//    int a[] = {4, 4, 5, 6, 12, 59};
//    int index = binarySearhLast(a, 4, 6);
//    NSLog(@"search Index: %d", index);
    
    int a[] = {1, 2, 1};
    double x = 3;
    int n = 2;
    int i = 2;
//    double result = f1(n, a, x);
//    NSLog(@"%f", result);
//    MyPrint(5);
//   sum =  sumD(4);
    sum = Polynomail(a, i, x, n);
    printf("%f", sum);
}

@end
